#include<bits/stdc++.h>
#define int long long
using namespace std;
void fileopen(string s)
{
    freopen((s+".in").c_str(),"r",stdin);
    freopen((s+".out").c_str(),"w",stdout);
}
int a[200003],n;
bool c[200003];
int calc()
{
    int i,la=-1,lb=-1,res=0;
    for(i=1;i<=n;i++)
    {
        if(c[i])
        {
            if(a[i]==la)
            {
                res+=a[i];
            }
            la=a[i];
        }
        else
        {
            if(a[i]==lb)
            {
                res+=a[i];
            }
            lb=a[i];
        }
    }
    return res;
}
int dfs(int now)
{
    if(now==n+1)
    {
        return calc();
    }
    c[now]=true;
    int t=dfs(now+1);
    c[now]=false;
    t=max(t,dfs(now+1));
    return t;
}
int dp[107][107][107];
void sub2()
{
    memset(dp,0,sizeof(dp));
    int i,j,k;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<i;j++)
        {
            if(j!=i-1)
            {
                k=i-1;
                if(a[i]==a[j])
                {
                    dp[i+1][i][k]=max(dp[i+1][i][k],dp[i][j][k]+a[i]);
                }
                else
                {
                    dp[i+1][i][k]=max(dp[i+1][i][k],dp[i][j][k]);
                }
                if(a[i]==a[k])
                {
                    dp[i+1][j][i]=max(dp[i+1][j][i],dp[i][j][k]+a[i]);
                }
                else
                {
                    dp[i+1][j][i]=max(dp[i+1][j][i],dp[i][j][k]);
                }
                //cerr<<i<<' '<<j<<' '<<k<<' '<<dp[i][j][k]<<'\n';
                continue;
            }
            for(k=1;k<i-1;k++)
            {
                if(j==k)
                {
                    continue;
                }
                if(a[i]==a[j])
                {
                    dp[i+1][i][k]=max(dp[i+1][i][k],dp[i][j][k]+a[i]);
                }
                else
                {
                    dp[i+1][i][k]=max(dp[i+1][i][k],dp[i][j][k]);
                }
                if(a[i]==a[k])
                {
                    dp[i+1][j][i]=max(dp[i+1][j][i],dp[i][j][k]+a[i]);
                }
                else
                {
                    dp[i+1][j][i]=max(dp[i+1][j][i],dp[i][j][k]);
                }
                //cerr<<i<<' '<<j<<' '<<k<<' '<<dp[i][j][k]<<'\n';
            }
        }
    }
    int res=-1;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(i!=j)
            {
                res=max(res,dp[n+1][i][j]);
            }
        }
    }
    cout<<res<<'\n';
}
int f[2][2003][2003];
void sub3()
{
    memset(f,0,sizeof(f));
    int i,j,k,cur=1;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<i;j++)
        {
            if(j!=i-1)
            {
                k=i-1;
                if(a[i]==a[j])
                {
                    f[cur^1][i][k]=max(f[cur^1][i][k],f[cur][j][k]+a[i]);
                }
                else
                {
                    f[cur^1][i][k]=max(f[cur^1][i][k],f[cur][j][k]);
                }
                if(a[i]==a[k])
                {
                    f[cur^1][j][i]=max(f[cur^1][j][i],f[cur][j][k]+a[i]);
                }
                else
                {
                    f[cur^1][j][i]=max(f[cur^1][j][i],f[cur][j][k]);
                }
                //cerr<<i<<' '<<j<<' '<<k<<' '<<f[cur][j][k]<<'\n';
                continue;
            }
            for(k=1;k<i-1;k++)
            {
                if(j==k)
                {
                    continue;
                }
                if(a[i]==a[j])
                {
                    f[cur^1][i][k]=max(f[cur^1][i][k],f[cur][j][k]+a[i]);
                }
                else
                {
                    f[cur^1][i][k]=max(f[cur^1][i][k],f[cur][j][k]);
                }
                if(a[i]==a[k])
                {
                    f[cur^1][j][i]=max(f[cur^1][j][i],f[cur][j][k]+a[i]);
                }
                else
                {
                    f[cur^1][j][i]=max(f[cur^1][j][i],f[cur][j][k]);
                }
                //cerr<<i<<' '<<j<<' '<<k<<' '<<f[cur][j][k]<<'\n';
            }
        }
        cur^=1;
    }
    int res=-1;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(i!=j)
            {
                res=max(res,f[cur][i][j]);
            }
        }
    }
    cout<<res<<'\n';
}
void solve()
{
    int i;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    if(n<=15)
    {
        cout<<dfs(1)<<'\n';
        return;
    }
    if(n<=100)
    {
        sub2();
        return;
    }
    if(n<=2000)
    {
        sub3();
        return;
    }
    //cerr<<"\n\n";
}
signed main()
{
    fileopen("color");
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}
